package com.ai.zuochengyun.phase01.class01;

public class Code13_HeapSort {

    /**
     * 从上到下的方法实现(经典实现)
     * @param arr
     */
    private static void heapSort1(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }

        // 先将整个arr调整成一个大根堆
        // O(N)
        for (int i = 0; i < arr.length; i++) {
            // O(log(N))
            heapInsert(arr, i);
        }

        int heapSize = arr.length;
        // 将最大值换到了末尾，并且将需要排序的区间由[0, n-1] 调整到 [0, n-2]，最后一个数不用看，有点类似冒泡排序
        swap(arr, 0, --heapSize);
        // O(N)
        while (heapSize > 0) {
            // 底部值到了顶端后，需要进行heapify，重新将arr调整成大根堆
            // O(log(N))
            heapify(arr, 0, heapSize);
            // 继续执行交换操作
            // O(1)
            swap(arr, 0, --heapSize);
        }
    }

    /**
     * 从下到上的方法实现
     * @param arr
     */
    private static void heapSort2(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }

        // 先将整个arr调整成一个大根堆
        // O(N)
        for (int i = arr.length-1; i >=0 ; i--) {
            heapify(arr, i, arr.length);
        }

        int heapSize = arr.length;
        // 将最大值换到了末尾，并且将需要排序的区间由[0, n-1] 调整到 [0, n-2]，最后一个数不用看，有点类似冒泡排序
        swap(arr, 0, --heapSize);
        // O(N)
        while (heapSize > 0) {
            // 底部值到了顶端后，需要进行heapify，重新将arr调整成大根堆
            // O(log(N))
            heapify(arr, 0, heapSize);
            // 继续执行交换操作
            // O(1)
            swap(arr, 0, --heapSize);
        }
    }

    /**
     * 上浮
     * 复杂度O(log(N))
     *
     * @param arr
     * @param index
     */
    private static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 下沉
     * 复杂度O(log(N))
     *
     * @param arr      数组
     * @param index    当前所在下标
     * @param heapSize 堆的长度
     */
    private static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize ? arr[left] > arr[left + 1] ? left : left + 1 : left;
            if (arr[index] >= arr[largest]) {
                break;
            }
            index = largest;
            left = index * 2 + 1;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
